package algorithm.sort;

import java.util.Arrays;

/**
 * 计数排序：适合重复数字多，数字范围小的数组
 * 先找出数组a中最大的数字，根据最大数字可以生成一个最大下标为最大数字的数组 b;
 * 倒序遍历原数组a，根据数值跟b的下标对应进行累加出现的次数；
 * 再遍历数组b，把前后的元素数值累加
 * 最后倒序遍历原数组，根据累加的数组中的值定位元素出现的位置，放入临时数组c中，
 * 每定位一个数，累加数组b中对应下标的数值就减一
 */
public class CountingSortTest {

    public static void main(String[] args) {
        int[] arr = {6,3,8,2,9,1,4,5,7,13};
        sort(arr);
        System.out.println("result arr = " + Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        int len = arr.length;
        // 找出最大数
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < arr.length; i++){
            if(max < arr[i]){
                max = arr[i];
            }
        }

        // 根据最大数创建新数组
        int[] countArr = new int[max + 1];

        // 从后往前遍历原数组，在新数组上计数
        for(int i = len - 1; i >= 0; i--){
            countArr[arr[i]] += 1;
        }

        // 计数完成后，在新数组上完成从前往后的累加
        for(int i = 1; i < countArr.length; i++){
            countArr[i] += countArr[i - 1];
        }

        // 创建一个临时数组
        int[] tempArr = new int[len];
        // 从后往前遍历原数组，跟新数组匹配的值匹配，这个值即是最终的排序位置，每命中一次，这个值就减一
        for(int i = len - 1; i >= 0; i--){
           tempArr[--countArr[arr[i]]] = arr[i];
        }

        // 拷贝回原数组
        for(int i = 0; i < len; i++){
            arr[i] = tempArr[i];
        }
    }
}
